#ifndef __HEAP_FUNCTIONS__
#define __HEAP_FUNCTIONS__

template <int d, typename position, typename ordering, typename policy>
void make_heap(position, const ordering&, policy&);

#ifndef __HEAP_POLICY__
#include "heap_policy.cpp" // defines the heap policy
#endif
#ifndef __UTILITY_FUNCTIONS__
#include "utility_functions.cpp" // defines the functions needed by heap functions
#endif

template <int d, typename position, typename ordering, typename policy>
void pop_heap(position a, const ordering& less, policy& p) {
  typedef typename policy::index index;
  typedef typename policy::element element;
 
  index i = 0;
  index j = p.last_leaf();
  element x = *(a + j);
  *(a + j) = *(a + i);
  p.erase_last_leaf(a);
  sift_down<d, position, index, element, ordering, policy>(a, i, x, less, p);
}

template <int d, typename position, typename ordering, typename policy>
void make_heap(position a, const ordering& less, policy& p) {
  //std::cout << "before make_heap: d " << d ;
  //show(a, a + p.size());
  typedef typename policy::index index;
  typedef typename policy::element element;

  if (p.size() == 0) return;

  for(index l = p.last_leaf(); l >= 0; --l) {
    sift_down2<d, position, index, element, ordering, policy>(a, l, *(a + l), less, p);    
  }
  //std::cout << "- after make_heap: d " << d;
  //show(a, a + p.size());
}

template <int d, typename position, typename ordering, typename policy>
void sort_heap(position a, const ordering& less, policy& p) {
  while (p.size() > 1) {
    pop_heap<d, position, ordering, policy>(a, less, p);
  }
}

#include "is_sorted.c++" // defines cphstl::is_sorted
//#include "helperfunctions.cpp" // defines data generation routines
#include "input_generation.c++"

template <int d, typename position, typename ordering>
bool is_heap(position a, position b, const ordering& less) {
  heap_policy<d, position, ordering> p(b - a);
  if (p.size() <= 1) return true;
  typedef typename heap_policy<d, position, ordering>::index index;
  
  index j;
  for (index i = 0; i <= p.last_leaf(); ++i) {
    if(p.last_child(i) <= p.last_leaf()) {
      j = p.top_all_present(a, i, ordering());
      if (less(*(a + i), *(a + j))) return false;
    }
    else if(p.first_child(i) <= p.last_leaf()) {
      j = p.top_some_absent(a, i, ordering());
      if (less(*(a + i), *(a + j))) return false;
    }	
  }
  return true;
}

#include <algorithm>

template <int d, typename position, typename ordering>
void heapsort(position a, position b, const ordering& less) {
  typedef heap_policy<d, position, ordering> policy;
  policy p(b - a);

  typedef typename policy::element element;
  std::vector<element> t(b - a);
  std::copy(a, b, t.begin());
    
  std::sort(t.begin(), t.end(), ordering());

  //std::cout << "before make_heap: ";
  //show(a, b);

  make_heap<d, position, ordering, policy>(a, less, p);
  bool result = is_heap<d, position, ordering>(a, b, less);

  //std::cout << "before sort_heap:";
  //show(a, b);
  assert(result);

  //std::cout << "heap maded" << std::endl;

  sort_heap<d, position, ordering, policy>(a, less, p);

  //std::cout << "after sort_heap: ";
  //show(a, b);

  assert(cphstl::is_sorted(a, b, less));
  assert(std::equal(a, b, t.begin()));
}

template <int d, typename position, typename ordering, typename policy>
void sort(position a, position b, const ordering& less) {
  policy p(b - a);

  make_heap<d, position, ordering, policy>(a, less, p);
  sort_heap<d, position, ordering, policy>(a, less, p);
}

#ifdef TEST_HEAP_FUNCTIONS
#define test_heap_functions main
#endif

#include <iostream> // defines standard streams
#include <cassert> // defines assert
#include <cstdlib> // defines std:.size_t
#include <functional> // defines std::less
#include <algorithm> // defines std::copy

int test_heap_functions () {
  typedef std::size_t element;
  typedef element* position;
  typedef std::less<element> ordering;


  std::cout << "Testing pop_heap, make_heap and sort_heap" << std::endl;
  const std::size_t bign = 1200;
  const std::size_t repetitions = 5;
  element a[bign];

  for (std::size_t n = 0; n <= bign; ++n) {

    decreasing_sequence(a, a + n);
    heapsort<2, position, ordering>(a, a + n, ordering());
  
    increasing_sequence(a, a + n);
    heapsort<2, position, ordering>(a, a + n, ordering());
  
    zero_sequence(a, a + n);
    heapsort<2, position, ordering>(a, a + n, ordering());
  
    binary_sequence(a, a + n);
    heapsort<2, position, ordering>(a, a + n, ordering());

    for (std::size_t i = 0; i < repetitions; i++) {
      random_sequence(a, a + n);
      heapsort<2, position, ordering>(a, a + n, ordering());
    }
    std::cout << n << " ok" << std::endl;
  }
  return 0;
}

#endif // __HEAP_FUNCTIONS__

